Что (кто) такое Перечислимое множество - определение

Перечисли́мое мно́жество (эффекти́вно перечислимое, рекурси́вно перечислимое, полуразреши́мое множество) — множество конструктивных объектов (например, натуральных чисел), все элементы которого могут быть получены с помощью некоторого алгоритма. Дополнение перечислимого множества называется корекурсивно перечислимым. Всякое перечислимое множество является арифметическим. Корекурсивно перечислимое множество может не быть перечислимым, но всегда является арифметическим. Перечислимые множества соответствуют уровню ${\displaystyle \Sigma _{1}^{0}}$ арифметической иерархии, а корекурсивно перечислимые — уровню ${\displaystyle \Pi _{1}^{0}.}$

Всякое разрешимое множество является перечислимым. Перечислимое множество является разрешимым тогда и только тогда, когда его дополнение также перечислимо. Другими словами, множество является разрешимым в том и только том случае, когда оно и перечислимо, и корекурсивно перечислимо. Подмножество перечислимого множества может не быть перечислимым (и даже может не быть арифметическим).

Совокупность всех перечислимых подмножеств ${\displaystyle \mathbb {N} }$ является счётным множеством, а совокупность всех неперечислимых подмножеств ${\displaystyle \mathbb {N} }$ — несчётным.